package com.sicheng.lc.周赛.分类.模拟;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/29 21:10
 */
public class 构造限制重复的字符串 {
    //https://leetcode.cn/problems/construct-string-with-repeat-limit/
    public String repeatLimitedString(String s, int repeatLimit) {

        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }
        int need;
        StringBuilder res = new StringBuilder();

        for (int i = count.length - 1; i >= 0; i--) {
            if (count[i] > 0) {
                need = count[i] / repeatLimit;
                if (need == 0) {
                    for (int m = 0; m < count[i]; m++) {
                        res.append((char) (i + 'a'));
                    }
                }
                for (int k = i - 1; need != 0 && k >= 0; k--) {
                    if (count[k] > 0) {
                        if (count[k] < need) {
                            for (int m = 0; m < count[k]; m++) {
                                build(res, i, repeatLimit, k);
                            }
                            need -= count[k];
                            count[k] = 0;
                        } else {
                            for (int m = 0; m < need; m++) {
                                build(res, i, repeatLimit, k);
                            }
                            count[k] -= need;
                            need = 0;
                        }
                    }
                }
            }
        }


        return "";
    }

    private void build(StringBuilder res, int i, int repeatLimit, int k) {
        for (int limit = repeatLimit; limit > 0; limit--) {
            res.append((char) (i + 'a'));
        }
        res.append((char) (k + 'a'));
    }
}
